Network processors are generally used for analyzing and processing packet data for routing and switching packets in a variety of applications, such as network surveillance, video transmission, protocol conversion, voice processing, and internet traffic routing. Early types of network processors were based on software-based approaches with general-purpose processors, either singly or in a multi-core implementation, but such software-based approaches are slow. Further, increasing the number of general-purpose processors had diminishing performance improvements, or might actually slow down overall network processor throughput. Newer designs add hardware accelerators in a system on chip (SoC) architecture to offload certain tasks from the general-purpose processors, such as encryption/decryption, packet data inspections, and the like. These newer network processor designs are traditionally implemented with either i) a non-pipelined SoC architecture or ii) a fixed pipeline SoC architecture.
In a typical non-pipelined SoC architecture, general-purpose processors are responsible for each action taken by acceleration functions. A non-pipelined SoC architecture provides great flexibility in that the general-purpose processors can make decisions on a dynamic, packet-by-packet basis, thus providing data packets only to the accelerators or other processors that are required to process each packet. However, significant software overhead is involved in those cases where multiple accelerator actions might occur in sequence.
In a typical fixed-pipeline SoC architecture, packet data flows through the general-purpose processors and/or accelerators in a fixed sequence regardless of whether a particular processor or accelerator is required to process a given packet. For example, in a fixed sequence, a single accelerator within the fixed pipeline cannot be employed without employing the entire fixed pipeline. This fixed sequence might add significant overhead to packet processing and has limited flexibility to handle new protocols, limiting the advantage provided by using the accelerators.
Network processors implemented as an SoC having multiple processing modules might typically classify an incoming packet to determine which of the processing modules will perform operations for the particular packet or flow of packets. Typical packet classification algorithms might perform a hashing operation on a portion of the packet data to determine a flow identifier of the packet. The hash value might be employed as an index into a lookup table storing identifiers of the various flows that are active within the network processor. In a typical network processor, millions of flows might be active at a given time and the storage requirements for the lookup table can become large. For example, a hash processor might need to traverse large linked lists for the lookup tables, and performance degradation is correlated to the size of the linked lists. Thus, efficient hash processors need improved processing and management of large linked lists.